﻿/**
 * @file array.h
 * @author septem (jsm920@outlook.com)
 * @brief array相当于c++的 vector<> 实现动态数组功能，数组可随push动态增大，可代替 stack 功能；
 * 所保存的数据不会因 push/pop 操作而发生在内存中移动的现象(相当于不会因push而引起 vector<>::iterator 失效)。
 * 但是 unshift/shift/insert/erase/shrink 会可能会导致数据发生移动
 * array2_t 相当于c++的 vector<> 实现动态数组功能，数组可随push动态增大，但可能会引起 原有数据在内存
 * 中发生移动(相当于可能会因push而引起 vector<>::iterator 失效)。
 * @version 0.1
 * @date 2024-12-09
 * 
 * @copyright Copyright (c) 2024
 * @note 概念：
 *  容器：可保存相同数据大小的结构体。
 *  变长容器：可以改变大小以适应不断增涨的数据的容器
 *  元素：保存在容器中的数据，同一个结构体中元素具有相同大小，并且分为元素大小和占用空间大小。
 *      元素在内存中的地址可能会向sizeof(void*)的整数倍取整。
 *  块：预分配的用于保存元素的内存块，使用链表方式管理。
 *  遍历：通过ArrayIterator类函数遍历
 * @note 遍历 array_t 方法 请查看 struct arrayiterator_t
 */
#ifndef _HEAD_ARRAY_
#define _HEAD_ARRAY_
#if defined(_WIN32) && defined(_MSC_VER)
#include <stdio.h>
#include <malloc.h> // _malloca() 栈上分配空间的函数
#elif defined(__linux__)
#include <stdio.h>
#endif
#ifndef roundup
#if defined(_WIN32) && defined(_MSC_VER)
//对 x 向上取 y 的整数倍
#define  roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y))
#elif defined(__linux__)
//对 x 向上取 y 的整数倍
#define  roundup(x, y) 			    \
({							        \
	typeof(y) __y = y;				\
	(((x) + (__y - 1)) / __y) * __y;\
})
#endif
#endif
/**
 * @brief 块链表,用于保存元素
 * 
 */
typedef struct arrayblock_t
{
    struct arrayblock_t*   pabPrev; //
    struct arrayblock_t*   pabNext; 
    unsigned int           cntCapacity; // 能容下 elem 数量
    unsigned int           cntElem; // 已保存的数据数量
    unsigned char          data[]; //数据起始地址
}arrayblock_t;

/**
 * @brief 可变长的数组容器结构
 * 
 */
typedef struct array_t
{
    struct arrayblock_t*   pabBeg; // 第一个 块(如果array_t*为空，则第一个块无元素，否侧 第一个块必须有元素)
    struct arrayblock_t*   pabEnd; // 最后一个块
    struct arrayblock_t*   pabTail; //最后一个包含数据的块
    unsigned int           cntCapacity; // 能容下 elem 数量
    unsigned int           cntElem; // 已保存的数据数量
    unsigned int           szElem; // 元素大小,单位 byte
    unsigned int           cntGrow; // 每次 Malloc增加的szElem数量
    // unsigned int                 cntGrow:(sizeof(unsigned int)*8-1); // 元素是否是需要调用 free
    // unsigned int                 signNeedFree:1; // 元素是否是需要调用 free
}array_t;

/**
 * @brief array_t 的 iterator,可使用 arrayiterator_t 类函数遍历 array_t
 * @note
 * ```c
 * // 从后向前遍历全部元素
 * for(arrayiterator_t* pai = ArrayIteratorInit(pa,-1); pai != NULL; pai = ArrayIteratorPrev(pai) )
 * {
 *      sometype_t* pdata = (sometype_t*)ArrayIteratorDataPtr(pai);
 *      // some code
 * }
 * // 从前向后遍历全部元素
 * for(arrayiterator_t* pai = ArrayIteratorInit(pa,0); pai != NULL; pai = ArrayIteratorNext(pai) )
 * {
 *      sometype_t* pdata = (sometype_t*)ArrayIteratorDataPtr(pai);
 *      // some code
 * }
 * ```
 */
typedef struct arrayiterator_t
{
    array_t* pa;
    arrayblock_t* pab;
    // void* pdata;
    unsigned int pos; // 在 
    unsigned int posAB; //在 arrayblock_t 中的位置
}arrayiterator_t;

#if defined(_WIN32) && defined(_MSC_VER)
/**
 * @brief 在栈上获取一个 arrayiterator_t* 配合 以下语句使用
 * for(arrayiterator_t* pai = ArrayIteratorInit(pa,-1); pai != NULL; pai = ArrayIteratorPrev(pai) ){}
 * @param pa array_t 结构
 * @param pos 范围内 (-1-cntElem,cntElem)
 */
#define ArrayIteratorInit(pa, pos) ( ArrayIteratorInit2((arrayiterator_t*)_malloca(sizeof(arrayiterator_t)),(pa),(pos)))
#elif defined(__linux__)
/**
 * @brief 在栈上获取一个 arrayiterator_t* 配合 以下语句使用
 * for(arrayiterator_t* pai = ArrayIteratorInit(pa,-1); pai != NULL; pai = ArrayIteratorPrev(pai) )
 * @param pa array_t 结构
 * @param pos 范围内 (-1-cntElem,cntElem)
 */
#define ArrayIteratorInit(pa, pos) ({arrayiterator_t ai = {0};ArrayIteratorInit2(&ai,(pa),(pos));})
#endif
/**
 * @brief 初始化一个 arrayiterator_t
 * 
 * @param pai 
 * @param pa 
 * @param pos 范围内 (-1-cntElem,cntElem)
 * @return arrayiterator_t* 
 */
arrayiterator_t* ArrayIteratorInit2(arrayiterator_t* pai, array_t* pa, int pos);
/**
 * @brief 向前遍历 到达最前面 返回 NULL
 * 
 * @param pai 
 * @return arrayiterator_t* 
 */
arrayiterator_t* ArrayIteratorPrev(arrayiterator_t* pai);
/**
 * @brief 向后遍历 到达最后面 返回 NULL
 * 
 * @param pai 
 * @return arrayiterator_t* 
 */
arrayiterator_t* ArrayIteratorNext(arrayiterator_t* pai);

/**
 * @brief 从 当前遍历的 arrayiterator_t 获取正在遍历的数据
 * @param pai 正在使用的 arrayiterator_t
 */
#define ArrayIteratorDataPtr(pai) ((pai)->pab->data +  (pai)->posAB * (pai)->pa->szElem)

/**
 * @brief 获取 需要使用的内存的大小
 * 
 */
#define ArrayMemUsed(szElem, cnt) sizeof(array_t) +sizeof(arrayblock_t) + (szElem)*(cnt)
// #define ArrayMemUsed(szElem, cnt) sizeof(array_t) + \
//                                     sizeof(arrayblock_t) + \
//                                     ArrayMemElemUsed((szElem))*(cnt);

/**
 * @brief malloc 一个可增涨的空间， 最初能够保存 cnt 数量的 数据，每个数据大小为 szElem 将自动调用 ArrayInit 初始化
 *  可执行 push/pop操作而不改变原有元素的位置,也可使用 unshift/shift/insert/erase(可能会改变原有元素的位置)
 *  可通过 ArrayIterator 类函数遍历
 * @param szElem 要保存的元素的大小
 * @param cnt 要预分配保存的元素的初始数量
 * @return array_t* 成功返回 array_t*; 失败返回NULL
 * @note 注意分配的内存空间是未初始化的。
 *  不再使用应通过 ArrayFree 回收内存
 */
array_t* ArrayMalloc(unsigned int szElem, unsigned int cnt);
/**
 * @brief free 包括 array_t* 在内的所有申请的内存
 * 
 * @param pa 通过 ArrayMalloc分配的 array_t*
 * @return void 无返回值
 */
void ArrayFree(array_t* pa);
/**
 * @brief  * @brief 初始化已分配好的一段空间，ArrayMalloc 调用 ArrayInit 来初始化。
 * 也可以自行分配空间（单位:bytes）（通过ArrayMemUsed来计算需要分配空间大小）
 * 
 * @param pa 由ArrayMalloc分配或自行分配的内存（通过ArrayMemUsed来计算需要分配空间大小）
 * @param szElem 准备保存的元素的大小
 * @param cnt 预计保存的元素的数量
 * @note 注意分配的内存空间是未初始化的。
 * @return array_t* 
 * @note 不再使用应通过 ArrayUninit 回收内存
 */
array_t* ArrayInit(array_t* pa, unsigned int szElem, unsigned int cnt);
/**
 * @brief free  所有的array_t* pa另外申请的块，但不包括array_t* pa自身
 * 
 * @param pa 通过 ArrayInit 初始化的 array_t*
 */
void ArrayUninit(array_t* pa);

/**
 * @brief 重新 malloc 内存，将所有数据移动到同一段内存之中
 * 
 * @param pa 
 * @return array_t* 
 */
array_t* ArrayShrink(array_t* pa);
/**
 * @brief 将 pa2 from开始的 cnt 数量的元素连接到 pa 的尾部(要求pa 和 pa2保存的是同一类数据)
 * 
 * @param pa 
 * @param pa2 
 * @param from 
 * @param cnt 
 * @return array_t* 
 * @note 未测试
 */
array_t* ArrayAssign(array_t* pa, array_t* pa2,unsigned int from,unsigned int cnt);
/**
 * @brief 截取 pa 中的一部分,生成一个新的array_t* 不再使用时需要调用 ArrayFree()
 * 
 * @param pa 
 * @param from 
 * @param cnt 
 * @return array_t* 
 */
array_t* ArraySub(array_t* pa, unsigned int from,unsigned int cnt);
/**
 * @brief 向尾部压入一个元素(元素大小在array_t*申请或初始化时传入), 已有数据不会在内存中移动
 * 
 * @param pa 
 * @param data 准备传入的元素，如果是 NULL,则返回未初始化的空间，但可以向其中写数据
 * @return void* 返回压入的元素地址，如果 data为 NULL， 则返回的地址空间未初始化
 * @example int d = 1; int* pi = ArrayPush(pa, &d);// 注意，pi != &d
 *          int *pi2 = ArrayPush(pa, NULL); (*pi2) = 100; 
 */
void* ArrayPush(array_t* pa, void* data );
/**
 * @brief 尾部弹出一个数据（已有数据不会发生移动）
 * 
 * @param pa 
 */
void ArrayPop(array_t* pa);
/**
 * @brief 在最前面插入一个元素（已有数据可能会发生移动）
 * 
 * @param pa 
 * @param data 
 * @return void* 
 */
void* ArrayUnshift(array_t* pa, void* data );

/**
 * @brief 从最前面删除一个元素（已有元素可能会发生移动）
 * 
 * @param pa 
 * @return void* 
 */
void ArrayShift(array_t* pa);
/**
 * @brief 从中间插入一些元素，注意，其它元素可以发生移动(对数组进行插入操作性能不好)
 * 
 * @param pa 
 * @param datas
 * @param from 
 * @param cnt 
 * @return int
 * @note 部分测试是OK的
 */
void* ArrayInsert(array_t* pa,void* data,unsigned int from, unsigned int cnt);
/**
 * @brief 从中间删除一些元素，注意，其它元素可以发生移动(对数组进行删除操作性能不好)
 * 
 * @param pa 
 * @param from 
 * @param cnt 
 * @return void* 
 * @note 已完成测试 202501271726
 */
void ArrayErase(array_t* pa,unsigned int from, unsigned int cnt);
/**
 * @brief 检查 pa 元素长度
 * 
 * @param pa 
 * @return int 
 */
#define ArraySize(pa) (pa)->cntElem
/**
 * @brief 检查pa 元素的容量
 * 
 */
#define ArrayCapacity(pa) (pa)->cntCapacity
/**
 * @brief Increase the capacity of the vector (the total number of elements that the vector can hold without requiring reallocation) 
 * to a value that's greater or equal to new_cap. If new_cap is greater than the current capacity(), new storage is allocated, 
 * otherwise the function does nothing.reserve() does not change the size of the vector. 
 * 
 * @param pa 
 * @param cnt 
 * @return array_t* 
 */
array_t* ArrayReserve(array_t* pa, unsigned int cnt);
/**
 * @brief 清空数据 
 * 
 * @param pa 
 */
void ArrayClear(array_t* pa);
/**
 * @brief Resizes the container to contain count elements, does nothing if count == size().

If the current size is greater than count, the container is reduced to its first count elements.

If the current size is less than count, then:
1) Additional default-inserted elements are appended.
2) Additional copies of value are appended.
 * 
 * @param pa 
 * @param cnt 
 * @return int 
 */
int ArrayResize(array_t* pa, unsigned int cnt);
/**
 * @brief 
 * 
 * @param pa 
 * @param pos1 
 * @param pos2 
 */
void ArraySwap(array_t* pa, unsigned int pos1, unsigned int pos2);
/**
 * @brief 对 pa 内元素进行排序，调用qsort
 * 
 * @param pa 
 * @param compar 
 */
void ArraySort(array_t* pa, int(*compar)(const void*,const void*));
/**
 * @brief 获取 pos 位置的数据指针, pos 可以是有效范围内的负值 超过范围返回NULL
 * 
 * @param pa 
 * @param pos 范围内 (-1-cntElem,-1]或 [0,cntElem)
 * @return void* 
 */
void* ArrayAt(array_t* pa, int pos);
/**
 * @brief 获取 pos 位置的数据指针  超过范围返回NULL
 * 
 * @param pa 
 * @param pos 范围内 [0,cntElem)
 * @return void* 
 */
void* ArrayAt2(array_t* pa, unsigned int pos);
/**
 * @brief 获取第一个元素,如果 array_t 为空，返回 NULL
 * 
 * @param pa 
 * @return void* 
 */
void* ArrayFront(array_t* pa);

/**
 * @brief 获取最后一个元素,如果 array_t 为空，返回 NULL
 * 
 * @param pa 
 * @return void* 
 */
void* ArrayBack(array_t* pa);

/**
 * @brief 相当于对 元素的指针 pdata 进行++操作，返回array_t*下一个元素的指针（在[0,pa->cntElem) 范围内部是有效的，但是效率比较低）
 * 
 * @param pa 
 * @param pdata 
 * @return void* 
 */
void* ArrayNext(array_t* pa,void* pdata);

/**
 * @brief 相当于对 元素的指针 pdata 进行--操作，返回array_t*上一个元素的指针（在[0,pa->cntElem) 范围内部是有效的，但是效率比较低）
 * 
 * @param pa 
 * @param pdata 
 * @return void* 
 */
void* ArrayPrev(array_t* pa,void* pdata);

#ifdef _DEBUG
void array_print_positive_order_int(array_t* pa);
void array_print_negative_order_int(array_t* pa);
void array_print_int_by_at(array_t* pa);
void array_print_int_by_at2(array_t* pa);
#endif

/**
 * @brief array2_t 区别于 array_t 当预分配的块满了之后会调用 realloc 重新分配，没有中间block这个概念
 * array2_t 因为使用连续内存，所以直接使用 for(int i = 0; i != array2_t::cntElem; i++){} 来遍历
 * 
 */
typedef struct array2_t
{
    unsigned int                  cntElem; // 已保存的数据数量
    unsigned int                  cntCapacity; // 能容下 elem 数量
    unsigned int                  szElem; // 元素大小,单位 byte
    unsigned int                  cntGrow; //元素每次增加的数量
    void*                   pdata; //数据
}array2_t;
/**
 * @brief 获取 调用 Array2Init 所需要内存
 * 
 */
#define Array2MemUsed(szElem, cnt) sizeof(array2_t)
/**
 * @brief 申请一个 array2_t 初始 capactity 为 szElem * cnt 
 * 
 * @param szElem 
 * @param cnt 
 * @return array2_t* 
 */
array2_t* Array2Malloc(unsigned int szElem, unsigned int cnt);
/**
 * @brief 完全注销一个 array2_t* 包括 pa
 * 
 * @param pa 
 */
void Array2Free(array2_t* pa);
/**
 * @brief 根据已申请的 array2_t* pa 初始化
 * 
 * @param pa 
 * @param szElem 
 * @param cnt 
 * @return array2_t* 
 */
array2_t* Array2Init(array2_t* pa, unsigned int szElem, unsigned int cnt);
/**
 * @brief Array2Init() 的反操作，注销一个 array2_t* 但不包括 pa 
 * 
 * @param pa 
 */
void Array2Uninit(array2_t* pa);
/**
 * @brief 向 array2_t* pa 尾部插入一个数据 data （压栈）
 * 
 * @param pa 
 * @param data 
 * @return void* 
 */
void* Array2Push(array2_t* pa, void* data);
/**
 * @brief 从array2_t* pa 尾部删除一个数据 （弹栈）
 * 
 * @param pa 
 */
void Array2Pop(array2_t* pa);
/**
 * @brief 直接把 pdata 及 pdata 以上数据全部弹出
 * 
 * @param pa 
 * @param data 
 */
void Array2PopTo(array2_t* pa, void* pdata);
/**
 * @brief 根据 pos 获取 array2_t* pa 中的数据，pos 范围 [1-array2_t::cntElem, array2_t::cntElem-1]
 *  -1指最后个数据，当不在范围返回 NULL
 * 
 * @param pa 
 * @param pos 
 * @return void* 
 */
void* Array2At(array2_t* pa, int pos);
/**
 * @brief 根据 pos 获取 array2_t* pa 中的数据，pos 范围 [0, array2_t::cntElem-1]
 * 
 * @param pa 
 * @param pos 
 * @return void* 
 */
void* Array2At2(array2_t* pa, unsigned int pos);

/**
 * @brief 在栈中查找 ptr, 需要传入比较两个数据是否相同的函数
 * 
 * @param pa 
 * @param ptr 
 * @param compar 
 * @return unsigned int 
 */
unsigned int Array2Search(array2_t* pa, const void* ptr, int (*compar)(const void*, const void*));
/**
 * @brief 根据 pdata 获取 前一个对象，注意 pdata一定要是栈中对象
 * 
 * @param pa 
 * @param pdata 
 * @return void* 
 */
void* Array2Prev(array2_t* pa, void* pdata);
/**
 * @brief 
 * 
 * @param pa 根据 pdata 获取 后一个对象，注意 pdata一定要是栈中对象
 * @param pdata 
 * @return void* 
 */
void* Array2Next(array2_t* pa, void* pdata);
/**
 * @brief 
 * 
 * @param pa 在 from 之前 插入 cnt 元素
 * @param datas 
 * @param from 
 * @param cnt 
 * @return void* 
 */
void* Array2Insert(array2_t* pa,void* datas,unsigned int from, unsigned int cnt);

/**
 * @brief 
 * 
 * @param pa 从 from　开始删除 最多 cnt元素
 * @param from 
 * @param cnt 
 * @return void* 
 */
void* Array2Erase(array2_t* pa,unsigned int from, unsigned int cnt);
/**
 * @brief 根据指针计算 数据 序号
 * 
 * @param pa 
 * @param ptr 
 * @return unsigned int 
 */
unsigned int Array2Pos (array2_t* pa, void* ptr);
#define Array2At3(pa, pos) (void*)((char*)(pa)->pdata + (pos) * (pa)->szElem) //不检查pos 直接计算偏移，有可能是无效数据，用于循环
#define Array2Size(pa) (pa)->cntElem // 获取 当前数据数量，用于循环

typedef array2_t stack2_t; //声明一个栈  @see array2_t
#define Stack2MemUsed() sizeof(stack2_t)
#define Stack2Malloc(szElem, cnt) Array2Malloc((szElem),(cnt)) //定义申请一个栈空间 @see @fn Array2Malloc
#define Stack2Free(pbts) Array2Free((pbts)) //定义注销一个栈空间 @see @fn Array2Free
#define Stack2Init(pbts,szElem, cnt) Array2Init((pbts), (szElem), (cnt)) //定义初始化一个栈空间 @see @fn Array2Init
#define Stack2Uninit(pbts) Array2Uninit((pbts)) //定义反初始化一个栈空间 @see @fn Array2Uninit
#define Stack2Push(pbts,ptr) Array2Push((pbts),(ptr)) //定义向栈空间压入一个 data @see @fn Array2Push
#define Stack2Pop(pbts) Array2Pop((pbts)) //定义从栈空间弹出一个 stack_t* 指针 @see @fn Array2Pop
#define Stack2PopTo(pbts, pdata) Array2PopTo((pbts),(pdata)) // 直接把 pdata 及 pdata 以上数据全部弹出
#define Stack2At(pbts, pos) Array2At((pbts), (pos)) //定义查栈空间 pos (可正可负)位置的 stack_t* 指针 @see @fn Array2At
#define Stack2At2(pbts,abs_pos) Array2At2((pbts), (abs_pos)) //定义查栈空间 pos位置的 stack_t* 指针 @see @fn Array2At2
#define Stack2Next(pbts, pdata) Array2Next((pbts), (pdata)) // 定义查栈空间 pdata 前一个元素(栈底方向)，
#define Stack2Prev(pbts, pdata) Array2Prev((pbts), (pdata)) // 定义查栈空间 pdata 后一个元素(栈顶方向)，
#define Stack2Search(pbts, ptr, compar) Array2Search((pbts), (ptr),(compar)) //在栈上查找一个元素，需要传入比较函数
#define Stack2Size(pbts) Array2Size((pbts)) // 获取 当前数据数量，用于循环
#define Stack2At3(pbts, pos) Array2At3((pbts), (pos)) //不检查pos 直接计算偏移，有可能是无效数据，用于循环
#define Stack2Erase(pbts, from, cnt) Array2Erase((pbts), (from), (cnt)) // 从栈上删除一些数据
#define Stack2Pos(pbts, ptr) Array2Pos((pbts),(ptr)) //根据指针计算 数据 序号

// typedef array_t stack_t; //声明一个栈  @see array_t // 在linux下 stack_t已定义,不再使用
#define StackMemUsed(szElem, cnt) ArrayMemUsed((szElem),(cnt)) // 获取预分配的空间大小
#define StackMalloc(szElem, cnt) ArrayMalloc((szElem),(cnt)) //定义申请一个栈空间 @see @fn ArrayMalloc
#define StackFree(pbts) ArrayFree((pbts)) //定义注销一个栈空间 @see @fn ArrayFree
#define StackInit(pbts,szElem, cnt) ArrayInit((pbts), (szElem), (cnt)) //定义初始化一个栈空间 @see @fn Array2Init
#define StackUninit(pbts) ArrayUninit((pbts)) //定义反初始化一个栈空间 @see @fn ArrayUninit
#define StackPush(pbts,ptr) ArrayPush((pbts),(ptr)) //定义向栈空间压入一个 data @see @fn ArrayPush
#define StackPop(pbts) ArrayPop((pbts)) //定义从栈空间弹出一个 array_t* 指针 @see @fn ArrayPop
// #define StackPopTo(pbts, pdata) ArrayPopTo((pbts),(pdata)) // 直接把 pdata 及 pdata 以上数据全部弹出
#define StackAt(pbts, pos) ArrayAt((pbts), (pos)) //定义查栈空间 pos (可正可负)位置的 array_t* 指针 @see @fn ArrayAt
#define StackAt2(pbts,abs_pos) ArrayAt2((pbts), (abs_pos)) //定义查栈空间 pos位置的 array_t* 指针 @see @fn Array2At2
#define StackNext(pbts, pdata) ArrayNext((pbts), (pdata)) // 定义查栈空间 pdata 前一个元素(栈底方向)，
#define StackPrev(pbts, pdata) ArrayPrev((pbts), (pdata)) // 定义查栈空间 pdata 后一个元素(栈顶方向)，
// #define StackSearch(pbts, ptr, compar) ArraySearch((pbts), (ptr),(compar)) //在栈上查找一个元素，需要传入比较函数
#define StackSize(pbts) ArraySize((pbts)) // 获取 当前数据数量，用于循环
#define StackErase(pbts, from, cnt) ArrayErase((pbts), (from), (cnt)) // 从栈上删除一些数据
// #define StackPos(pbts, ptr) ArrayPos((pbts),(ptr)) //根据指针计算 数据 序号


#endif // end of define _HEAD_ARRAY_
